package main

import (
	"fmt"
)

func main() {
	res1 := letterCombinations("23")
	for _, v := range res1 {
		fmt.Printf("%s\n", v)
	}
}

var letterMap = map[string]string{
	"0": " ",    //0
	"1": "",     //1
	"2": "abc",  //2
	"3": "def",  //3
	"4": "ghi",  //4
	"5": "jkl",  //5
	"6": "mno",  //6
	"7": "pqrs", //7
	"8": "tuv",  //8
	"9": "wxyz", //9
}

func letterCombinations(digits string) []string {
	res := make([]string, 0)
	if len(digits) == 0 {
		return res
	}
	backtrack(&res, "", digits)
	return res
}

func backtrack(res *[]string, combination string, nextDigits string) {
	if nextDigits == "" {
		*res = append(*res, combination)
		return
	}

	digit := nextDigits[:1]
	letters := letterMap[digit]
	for _, c := range letters {
		backtrack(res, combination+string(c), nextDigits[1:])
	}
}
